#ifndef _IMPLEMENTATION_HPP
#define _IMPLEMENTATION_HPP

#include "interface.hpp"
#include "data.hpp"

#include <CL/cl.hpp>

#include <string>
#include <iostream>
#include <limits>


static inline void checkErr(cl_int err, const char * name){
    if (err != CL_SUCCESS) {
            std::cerr << "ERROR: " << name << " (" << err << ")" << std::endl;
            exit(EXIT_FAILURE);
    }
}

#define HASH0(from, to, modulo) \
(to) = (from);           \
(to) -= ((to)<<6);    \
(to) ^= ((to)>>17);   \
(to) -= ((to)<<9);    \
(to) ^= ((to)<<4);    \
(to) -= ((to)<<3);    \
(to) ^= ((to)<<10);   \
(to) ^= ((to)>>15);   \
(to) %= (modulo);









#define HASH1(from, to, modulo)             \
(to) = (from);                              \
(to) ^= ((to) >> 20) ^ ((to) >> 12);        \
(to) = (to) ^ ((to) >> 7) ^ ((to) >> 4);    \
(to) %= (modulo);




class Cockoo{
    std::vector<unsigned> hashed [2];
    //std::vector<unsinged> hashed2;
    unsigned notPresent;
    unsigned size;
    unsigned maxTries;

    unsigned tries;
    unsigned maxTry;

    //typedef unsigned (Cockoo::*ptr_to_some_member)(unsigned a);
    //ptr_to_some_member hashes[2];
public:
    inline unsigned hash1(unsigned a){
        a -= (a<<6);
        a ^= (a>>17);
        a -= (a<<9);
        a ^= (a<<4);
        a -= (a<<3);
        a ^= (a<<10);
        a ^= (a>>15);
        return a;
    }
    inline unsigned hash2(unsigned a){
        a ^= (a >> 20) ^ (a >> 12);
        return a ^ (a >> 7) ^ (a >> 4);
    }
    inline bool insert(unsigned i){
        for( unsigned j = 0; j < maxTries; ++j){
            maxTry = std::max(j + 1, maxTry);
            ++tries;
            if ( tries == std::numeric_limits<unsigned>::max() ){
                std::cerr << "overflow tries" << std::endl;
            }

            //unsigned idx = j & 1;
            unsigned pos;
            HASH0( i, pos, size );
            unsigned newI = hashed[0][pos];
            hashed[0][pos] = i;
            if (newI == notPresent)
                return true;

            i = newI;

            HASH1( i, pos, size );
            //pos = hash2(i) % size;
            newI = hashed[1][pos];
            hashed[1][pos] = i;
            if (newI == notPresent)
                return true;
            i = newI;
        }
        return false;
    }
    inline bool find(unsigned i){
        //unsigned pos = hash1(i) % size;
        unsigned pos;
        HASH0( i, pos, size );
        if ( hashed[0][pos] == i)
            return true;
        //pos = hash2(i) % size;
        HASH1( i, pos, size );
        if ( hashed[1][pos] == i)
            return true;
        return false;
    }
    Cockoo(const std::vector<unsigned> & data ){
        tries = 0; maxTry = 0;
        maxTries = 10000;
        notPresent = 0;//min - 1;
        size = 2 * data.size();

//        hashes[0] = &Cockoo::hash1;
//        hashes[1] = &Cockoo::hash2;

        hashed[0].assign(size,notPresent);
        hashed[1].assign(size,notPresent);

        for( size_t i = 0; i < data.size(); ++i){
            //std:: cerr << i << std::endl;
            if ( ! insert(data[i]) ){
                std::cerr << "failed at " << i << " from " << data.size() << std::endl;
                break;
            }
        }
        std::cout << "avg tries: " <<  ((float)tries)/data.size() << std::endl;
        std::cout << "max tries: " <<  maxTry << std::endl;
    }
    void findDuplicates(const std::vector<unsigned> & data,  std::vector<unsigned> & result){
        for( size_t i = 0; i < data.size(); ++i){
            if (find(data[i]))
                result.push_back(data[i]);
        }
        std::cerr << "result.size(): " << result.size() << std::endl;
    }

};


/*
 *  * Final implementation of the tested OCL program.
 *   */
class OCLProgram_Implementation : public OCLProgram
{
private:
    cl::Buffer * mBuffers;
    cl::CommandQueue * mCommandQueue;
    std::map<std::string, cl::Kernel> * mCompiledKernels;


    cl::Kernel & getKernel(const std::string & str){
        return (*mCompiledKernels)[str];
    }

    enum {
        IN = 0,
        TMP = 1,
        OUT = 2,
        COCKOO = 3,
        IN2 = 4
    };

    cl::Buffer & getBuffer( int type ){
        return (mBuffers[type]);
    }
    cl::CommandQueue & getCommandQueue(){
        return *mCommandQueue;
    }

    inline void dbgMsg( bool verbose,Stopwatch * stopwatch, const char * str){
        if (verbose){
            stopwatch->stop();
            std::cout << str << stopwatch->getMiliseconds() << " ms" << std::endl;
            stopwatch->start();
        }
    }


    void prepareInput(){

	size_t size = mDataIn.set1.size() + mDataIn.set2.size();
        size_t bytes_size = size * sizeof(unsigned);

        cl_int err = getCommandQueue().enqueueWriteBuffer(getBuffer(IN),CL_FALSE, 0, bytes_size/2, (const void *) &mDataIn.set1.front() );
        checkErr(err, "CommandQueue::enequeueWriteBuffer");

        err = getCommandQueue().enqueueWriteBuffer(getBuffer(IN2),CL_FALSE, 0, bytes_size/2, (const void *) &mDataIn.set2.front() );
        checkErr(err, "CommandQueue::enequeueWriteBuffer");

        err = getCommandQueue().finish();
        checkErr(err, "CommandQueue::enequeueWriteBuffer::finish");


     //   zeroBuffer( TMP, size );

        zeroBuffer(COCKOO, size * 2);


        /*wait till writes are finished
 *         commandQueue.finish();*/
    }



   void zeroBuffer(int type, size_t length){
	cl_int err;
	length = (length + 3) / 4;
/*      cl_int4 pattern;
        pattern.s[0] = 0;
        pattern.s[1] = 0;
        pattern.s[2] = 0;
        pattern.s[3] = 0;
        cl_int err = getCommandQueue().enqueueFillBuffer(getBuffer(type),pattern,0,length);
*/
        cl::Kernel & zero = getKernel("zero");
	err = zero.setArg( 0, getBuffer(type) );
	checkErr(err,"zero.setArg");
	err = getCommandQueue().enqueueNDRangeKernel( zero,cl::NullRange,cl::NDRange(length),cl::NullRange );
        checkErr(err, "zefoBuffer::enqueue");
        err = getCommandQueue().finish();
        checkErr(err, "zefoBuffer::finish");

    }

   void cockooHash(){

       size_t size = mDataIn.set1.size();
       cl_int err;

       cl::Kernel & hash = getKernel("cockooHash");

       err = hash.setArg( 0, getBuffer(IN) );
       checkErr(err,"cockooHash.setArg0");

       err = hash.setArg(1,getBuffer(COCKOO));
       checkErr(err,"cockooHash.setArg1");

       cl_uint s = 2 * size;
       err = hash.setArg( 2, sizeof(s), (void*) &s );
       checkErr(err,"cockooHash.setArg2");

       err = getCommandQueue().enqueueNDRangeKernel( hash,cl::NullRange,cl::NDRange(size),cl::NullRange );
       checkErr(err, "cockooHash::enqueue");
       err = getCommandQueue().finish();
       checkErr(err, "cockooHash::finish");

   }

   void cockooFind(){
       size_t size = mDataIn.set1.size();
       cl_int err;

       cl_uint s = 2 * size;

       cl::Kernel & cockooFind = getKernel("cockooFind");
       err = cockooFind.setArg( 0, getBuffer(IN2) );
       checkErr(err,"cockooFind::setArgument:0");
       err = cockooFind.setArg( 1, getBuffer(OUT) );
       checkErr(err,"cockooFind::setArgument:1");
       err = cockooFind.setArg( 2, getBuffer(COCKOO) );
       checkErr(err,"cockooFind::setArgument:2");
       err = cockooFind.setArg( 3, 1 * sizeof(cl_uint), (void *) NULL );    //local args
       checkErr(err,"cockooFind::setArgument:3");
       err = cockooFind.setArg( 4, sizeof(s), (void*) &s );
       checkErr(err,"cockooFind::setArgument:4");
       err = cockooFind.setArg( 5, getBuffer(TMP) );
       checkErr(err,"cockooFind::setArgument:5");


       err = getCommandQueue().enqueueNDRangeKernel( cockooFind,cl::NullRange,cl::NDRange(size), cl::NDRange(1024) );
       checkErr(err, "cockooFind::enqueue");
       err = getCommandQueue().finish();
       checkErr(err, "cockooFind::finish");

//       unsigned nGroups = size / 1024;
//       cl_uint dbg_ptr[nGroups + 3];
//       err = getCommandQueue().enqueueReadBuffer(getBuffer(TMP),CL_TRUE,0,sizeof(cl_uint) * (nGroups + 3), (void *)dbg_ptr);

//       printf("%d groups, %d threads, count %d\n", dbg_ptr[nGroups + 0],dbg_ptr[nGroups + 1], dbg_ptr[ nGroups + 2] );

//       unsigned resSize = 0;
//       for( size_t k = 0; k < nGroups; ++k){
//           resSize += dbg_ptr[k];
//       }
//       printf("%d groups, %d res_size\n", nGroups, resSize);
      // zeroBuffer( TMP, 3 );
   }

   void prefixSum(){
       cl_int err;
       cl_uint group_size = 1024;
       cl_uint work_size = mDataIn.set1.size();
       cl_uint number_groups = work_size / group_size;

       cl::Kernel & prefSum = getKernel("prefixSum");

       err = prefSum.setArg(0,getBuffer(TMP));
       checkErr(err, "prefixSum::setArg:0");
       err = prefSum.setArg(1,getBuffer(COCKOO));
       checkErr(err, "prefixSum::setArg:1");
       err = prefSum.setArg(2,getBuffer(IN2));
       checkErr(err, "prefixSum::setArg:2");
       err = prefSum.setArg( 3, group_size * 2 * sizeof(cl_uint), (void *) NULL );    //local args
       checkErr(err, "prefixSum::setArg:3");

       err = getCommandQueue().enqueueNDRangeKernel( prefSum,cl::NullRange,cl::NDRange(work_size/2),cl::NDRange(group_size/2) );
       checkErr(err, "prefixSum::ndrange");
       err = getCommandQueue().finish();
       checkErr(err, "prefixSum::finish");

       //err = getCommandQueue().enqueueReadBuffer(getBuffer(OUT),CL_TRUE,0,sizeof(cl_uint) * 2048 * 2, (void *)&data.front());
//////////////////

       cl::Kernel & prefSumC = getKernel("prefixSumC");
       err = prefSumC.setArg(0,getBuffer(IN2));
       checkErr(err, "prefixSumC::setArg:0");
       err = prefSumC.setArg(1,getBuffer(IN2));
       checkErr(err, "prefixSumC::setArg:1");
       cl_uint sz = number_groups / group_size;
       err = prefSumC.setArg(2,sizeof(cl_uint),&sz);
       checkErr(err, "prefixSumC::setArg:2");

       err = getCommandQueue().enqueueNDRangeKernel( prefSumC,cl::NullRange,cl::NDRange(1),cl::NDRange(1) );
       checkErr(err, "prefixSumC::ndrange");
       err = getCommandQueue().finish();
       checkErr(err, "prefixSumC::finish");

///////////////////////////////////////

       cl::Kernel & prefSumB = getKernel("prefixSumB");
       err = prefSumB.setArg(0,getBuffer(COCKOO));
       checkErr(err, "prefixSumB::setArg:0");
       err = prefSumB.setArg(1,getBuffer(TMP));
       checkErr(err, "prefixSumB::setArg:1");
       err = prefSumB.setArg(2,getBuffer(IN2));
       checkErr(err, "prefixSumB::setArg:2");
       err = prefSumB.setArg( 3, group_size * 2 * sizeof(cl_uint), (void *) NULL );    //local args
       checkErr(err, "prefixSumB::setArg:3");

       err = getCommandQueue().enqueueNDRangeKernel( prefSumB,cl::NullRange,cl::NDRange(work_size/2),cl::NDRange(group_size/2) );
       checkErr(err, "prefixSumB::ndrange");
       err = getCommandQueue().finish();
       checkErr(err, "prefixSumB::finish");
   }

   void runCopyByOffset(){
       cl_int err;
       cl::Kernel & copyByOffset = getKernel("copyByOffset");
       err = copyByOffset.setArg( 0, getBuffer(OUT) );
       checkErr(err, "copyByOffset::setArg:0");
       err = copyByOffset.setArg( 1, getBuffer(COCKOO) );
       checkErr(err, "copyByOffset::setArg:1");
       err = copyByOffset.setArg( 2, getBuffer(TMP) );
       checkErr(err, "copyByOffset::setArg:2");

       err = getCommandQueue().enqueueNDRangeKernel( copyByOffset,cl::NullRange,cl::NDRange(this->mDataIn.set1.size()), cl::NDRange(1024) );
       checkErr(err, "copyByOffset::enqueue");
       err = getCommandQueue().finish();
       checkErr(err, "copyByOffset::finish");

       cl_uint resSize;
       err = getCommandQueue().enqueueReadBuffer(getBuffer(OUT),CL_TRUE,0,sizeof(cl_uint) * 1, (void *)&resSize);
       checkErr(err, "copyByOffset::readResSize");
//       std::cout << "runCopy : result size " << resSize << std::endl;


       err = getCommandQueue().enqueueReadBuffer(getBuffer(COCKOO),CL_TRUE,0,sizeof(cl_uint) * resSize, (void *)&mDataOut.res.front());
       checkErr(err, "copyByOffset::readRes");

       mDataOut.res.resize(resSize,0);


   }


   void prefixSum0(){
       size_t size = 1024;
       std::vector<unsigned> data(4 * size,0);
       for( size_t t = 1; t <= 15; ++t){
           data[t - 1] = t;
       }
       for( size_t t = 1; t <= 15; ++t){
           data[1024 + t - 1] = t + 10;
       }

       cl_int err = getCommandQueue().enqueueWriteBuffer(getBuffer(TMP),CL_TRUE,0,sizeof(cl_uint) * size * 2, (void *)&data.front());
       checkErr(err, "prefixSum::write");
       getCommandQueue().finish();
       checkErr(err, "prefixSum::finish:1");

       zeroBuffer(OUT,4 * size);
       cl::Kernel & prefSum = getKernel("prefixSum");
       err = prefSum.setArg(0,getBuffer(TMP));
       checkErr(err, "prefixSum::setArg:0");
       err = prefSum.setArg(1,getBuffer(OUT));
       checkErr(err, "prefixSum::setArg:1");
       err = prefSum.setArg(2,getBuffer(COCKOO));
       checkErr(err, "prefixSum::setArg:2");
       err = prefSum.setArg( 3, size * 2 * sizeof(cl_uint), (void *) NULL );    //local args
       checkErr(err, "prefixSum::setArg:3");

       err = getCommandQueue().enqueueNDRangeKernel( prefSum,cl::NullRange,cl::NDRange(size),cl::NDRange(size/2) );
       checkErr(err, "prefixSum::ndrange");
       err = getCommandQueue().finish();
       checkErr(err, "prefixSum::finish");

       err = getCommandQueue().enqueueReadBuffer(getBuffer(OUT),CL_TRUE,0,sizeof(cl_uint) * 2048 * 2, (void *)&data.front());

       //////////////////////////////////////////////////////

//       for(size_t i = 0; i < data.size(); ++i){
//           if ( i % 16 == 0 ){
//               std::cout << std::endl;
//           }
//           if ( i == data.size() / 2 )
//               std::cout << std::endl << std::endl << "second: "<<std::endl;
//           std::cout << data[i] << " ";
//       }

//       std::cout << std::endl << std::endl << std::endl;

       ///////////////////////////////

       cl::Kernel & prefSumC = getKernel("prefixSumC");
       err = prefSumC.setArg(0,getBuffer(COCKOO));
       checkErr(err, "prefixSumC::setArg:0");
       err = prefSumC.setArg(1,getBuffer(COCKOO));
       checkErr(err, "prefixSumC::setArg:1");
       cl_uint sz = 2;
       err = prefSumC.setArg(2,sizeof(cl_uint),&sz);
       checkErr(err, "prefixSumC::setArg:2");

       err = getCommandQueue().enqueueNDRangeKernel( prefSumC,cl::NullRange,cl::NDRange(1),cl::NDRange(1) );
       checkErr(err, "prefixSumC::ndrange");
       err = getCommandQueue().finish();
       checkErr(err, "prefixSumC::finish");

       cl_uint d[2];
       err = getCommandQueue().enqueueReadBuffer( getBuffer(COCKOO),CL_TRUE,0,sizeof(cl_uint) * 2, (void *)d);
       std::cout << "partial sums:" << std::endl;
       std::cout << d[0] << std::endl;
       std::cout << d[1] << std::endl;


       err = getCommandQueue().enqueueReadBuffer( getBuffer(OUT),CL_TRUE,0,sizeof(cl_uint) * 2048 * 2, (void *)&data.front());


//       std::cout << std::endl << std::endl << "pref sum C: first: "<< std::endl;
//       std::cout << data[0] << std::endl;
//       std::cout << data[0 + 2048] << std::endl;

//       for(size_t i = 0; i < data.size(); ++i){
//           if ( i % 16 == 0 ){
//               std::cout << std::endl;
//           }
//           if ( i == data.size() / 2 )
//               std::cout << std::endl << std::endl << "pref sum C: second: "<<std::endl;
//           std::cout << data[i] << " ";
//       }

//       std::cout << std::endl << std::endl << std::endl;

      ///////////////////////

       cl::Kernel & prefSumB = getKernel("prefixSumB");
       err = prefSumB.setArg(0,getBuffer(OUT));
       checkErr(err, "prefixSumB::setArg:0");
       err = prefSumB.setArg(1,getBuffer(TMP));
       checkErr(err, "prefixSumB::setArg:1");
       err = prefSumB.setArg(2,getBuffer(COCKOO));
       checkErr(err, "prefixSumB::setArg:2");

       err = prefSumB.setArg( 3, size * 2 * sizeof(cl_uint), (void *) NULL );    //local args
       checkErr(err, "prefixSumB::setArg:3");

       err = getCommandQueue().enqueueNDRangeKernel( prefSumB,cl::NullRange,cl::NDRange(size),cl::NDRange(size/2) );
       checkErr(err, "prefixSumB::ndrange");
       err = getCommandQueue().finish();
       checkErr(err, "prefixSumB::finish");

       err = getCommandQueue().enqueueReadBuffer(getBuffer(TMP),CL_TRUE,0,sizeof(cl_uint) * 2048 * 2, (void *)&data.front());

//       std::cout << std::endl << std::endl << "pref sum B: first: "<< std::endl;

//       for(size_t i = 0; i < data.size(); ++i){
//           if ( i % 16 == 0 ){
//               std::cout << std::endl;
//           }
//         //  if ( i == data.size() / 2){
        //       std::cout << std::endl << std::endl << "pref sum B: second: "<< std::endl;
        //       break;
      //     }
    //       std::cout << data[i] << " ";
  //     }

//       std::cout << std::endl;





   }



    void computeMinMax( cl_uint * pmin, cl_uint * pmax){

        cl_int err;
        cl_uint num_src_items = (mDataIn.set1.size() + mDataIn.set2.size());

        cl_uint compute_units;
        size_t global_work_size;
        size_t local_work_size;
        size_t num_groups;
/*        clGetDeviceInfo( device, CL_DEVICE_MAX_COMPUTE_UNITS, sizeof(cl_uint), &compute_units, NULL);*/
                                                                                                                               
        compute_units = 512;
        cl_uint ws = 64;
        /*global_work_size = compute_units * 7 * ws; 7 wavefronts per SIMD*/
        global_work_size = compute_units * ws;
        while( (num_src_items / 4) % global_work_size != 0 )
            global_work_size += ws;
        local_work_size = ws;

        num_groups = global_work_size / local_work_size;

        cl::Kernel & minMaxP = getKernel("minMaxP");
        err = minMaxP.setArg( 0, getBuffer(IN) );
        checkErr(err,"minMaxP::setArgument:0");
        err = minMaxP.setArg( 1, getBuffer(OUT) );
        checkErr(err,"minMaxP::setArgument:1");
        err = minMaxP.setArg( 2, 1 * sizeof(cl_uint), (void *) NULL );    //local args
        checkErr(err,"minMaxP::setArgument:2");
        err = minMaxP.setArg( 3, 1 * sizeof(cl_uint), (void *) NULL );    //local args
        checkErr(err,"minMaxP::setArgument:3");
        err = minMaxP.setArg( 4, sizeof(num_src_items), (void*) &num_src_items );
        checkErr(err,"minMaxP::setArgument:4");
	err = minMaxP.setArg(5,getBuffer(TMP));
	checkErr(err,"minMaxP::setArgument:5");

        cl::Kernel & minMaxReduceP = getKernel("minMaxReduceP");
        err = minMaxReduceP.setArg( 0, getBuffer(OUT) );
        checkErr(err,"minMaxReduceP::setArgument:0");

        std::vector<cl::Event> events;
        events.push_back(cl::Event());
        cl::Event & ev = events.front();


        err = getCommandQueue().enqueueNDRangeKernel(
              minMaxP,cl::NullRange,cl::NDRange(global_work_size),cl::NDRange(local_work_size),0,&ev
        );
        checkErr(err,"commandQueue::enequeueNDRange(minMaxP)");
        err = getCommandQueue().enqueueNDRangeKernel(
              minMaxReduceP,cl::NullRange,cl::NDRange(num_groups),cl::NDRange(1),&events,NULL
        );
        checkErr(err,"commandQueue::enequeueNDRange(minMaxReduceP)");

        getCommandQueue().finish();
        cl_uint out[2];
        err = getCommandQueue().enqueueReadBuffer(getBuffer(OUT),CL_TRUE,0,sizeof(cl_uint) * 2, (void*)out);
	checkErr(err,"commandQueue::enequeueReadBuffer(Out)");
        *pmin = out[0];
        *pmax = out[1];

	cl_uint dbg_ptr[4];
	err = getCommandQueue().enqueueReadBuffer(getBuffer(TMP),CL_TRUE,0,sizeof(cl_uint) * 4, (void *)dbg_ptr);

	printf("%d groups, %d threads, count %d, stride %d\n", dbg_ptr[0],dbg_ptr[1], dbg_ptr[2],dbg_ptr[3] );

	zeroBuffer( TMP, 4 );
    }

    void checkMinMax(cl_uint min, cl_uint max){
        unsigned m1 = *std::min_element(mDataIn.set1.begin(),mDataIn.set1.end());
        unsigned m2 = *std::min_element(mDataIn.set2.begin(),mDataIn.set2.end());
        unsigned m = std::min(m1,m2);
        unsigned M1 = *std::max_element(mDataIn.set1.begin(),mDataIn.set1.end());
        unsigned M2 = *std::max_element(mDataIn.set2.begin(),mDataIn.set2.end());
        unsigned M = std::max(M1,M2);
        std::cout << "min element: " << (min == m ? "ok" : "fail") << std::endl;
        std::cout << "max element: " << (max == M ? "ok" : "fail") << std::endl;
    }


    void checkHistogram( const std::vector<cl_uint> & hist, cl_uint min, cl_uint max ){
        std::vector<cl_uint> myHist(hist.size() + 1, 0);
        cl_uint L = hist.size();
	float range = max - min;
	std::cout << "L: " << L << std::endl;
        for( size_t i = 0; i < mDataIn.set1.size(); ++i){
            float element = mDataIn.set1[i] - (float)min;
            cl_uint index = (element / range ) * L;
            ++myHist[index];
        }
        for( size_t i = 0; i < mDataIn.set2.size(); ++i){
            float element = mDataIn.set2[i] - (float)min;
            cl_uint index = (element / range) * L;
            ++myHist[index];
        }
        bool ok = true;
        for(size_t i = 0; i < hist.size(); ++i){
            if ( hist[i] != myHist[i]){
                ok = false;
	        std::cout << i  << " : hist:myHist : " << hist[i] << ":" << myHist[i] << std::endl;
	    }
        }
        std::cout << "histogram values: " << (ok ? "ok" : "fail") << std::endl;
    }

    void cockooImpl(){
        Stopwatch stopwatch(true);

        Cockoo c(this->mDataIn.set1);
        std::cout << "cockoo impl 1: " << stopwatch.getMiliseconds() << " ms" << std::endl;
        c.findDuplicates(this->mDataIn.set2,this->mDataOut.res);

        std::cout << "cockoo impl 2: " << stopwatch.getMiliseconds() << " ms" << std::endl;

        //std::sort(this->mDataOut.res.begin(), this->mDataOut.res.end() );
    }

    void computeBuckets( cl_uint L, cl_uint min, cl_uint max){

//	zeroBuffer( TMP, L);
        cl_int err;

        cl_uint num_src_items = (mDataIn.set1.size() + mDataIn.set2.size());
	cl_uint local_work_size = 4 * 64;
	size_t global_work_size = 512 * local_work_size;
	while( (num_src_items / 4) % global_work_size != 0)
		global_work_size += local_work_size;
        //size_t num_groups = global_work_size / local_work_size;

	zeroBuffer(TMP,L);

        cl::Kernel & histogram = getKernel("histogram");

        err = histogram.setArg( 0, getBuffer(IN) );
        checkErr(err,"histogram::setArgument:0");
        err = histogram.setArg( 1, getBuffer(TMP) );
        checkErr(err,"histogram::setArgument:1");
        err = histogram.setArg( 2, sizeof(cl_uint), (void*) &min );
        checkErr(err,"histogram::setArgument:2");
        err = histogram.setArg( 3, sizeof(cl_uint), (void*) &max );
        checkErr(err,"histogram::setArgument:3");
        err = histogram.setArg( 4, sizeof(cl_uint), (void*) &L );
        checkErr(err,"histogram::setArgument:4");
	err = histogram.setArg( 5, sizeof(cl_uint), (void*) &num_src_items);
	checkErr(err, "histogram::setArgument:5");
	err = histogram.setArg(6, sizeof(cl_uint) * local_work_size, (void*) NULL);
	checkErr(err,"histogram::setArgument:6");

        err = getCommandQueue().enqueueNDRangeKernel(histogram,cl::NullRange,cl::NDRange(global_work_size),cl::NDRange(local_work_size));
        checkErr(err,"commandQueue::enequeue(histogram)");
	
	std::vector<cl_uint> hist(L,0);

        err = getCommandQueue().finish();
        checkErr(err,"commandQueue::enequeue(histogram) - finish");
	
	err = getCommandQueue().enqueueReadBuffer(getBuffer(TMP),CL_TRUE,0,sizeof(cl_uint) * L, (void *) &hist.front());
	checkErr(err,"commandQueue::enequeueReadBuffer(TMP,hist)");
	checkHistogram(hist,min,max);	
	
    }
	
    void computeSerial(){
	std::vector<unsigned> s1 = mDataIn.set1;
	std::vector<unsigned> s2 = mDataIn.set2;
	std::vector<unsigned> result;
	result.reserve(std::min(s1.size(),s2.size()) );
	Stopwatch stopwatch(true);
	std::sort(s1.begin(),s1.end());
	std::sort(s2.begin(),s2.end());
	mergeJoin(s1,s2,result);
	stopwatch.stop();
	std::cout << "serial took: " << stopwatch.getMiliseconds() << " ms" << std::endl;
        std::cout << "serial. result.size(): " << result.size() << std::endl;
    }
    // loc memory size in bytes 49152

    void info(const std::vector<cl::Device> &devices){
        std::string off = "    ";
        for( size_t i = 0; i < devices.size(); ++i ){
            const cl::Device & device = devices[i];
            std::cout << "device: " << i << std::endl;
            cl_ulong inf;
            device.getInfo(CL_DEVICE_LOCAL_MEM_SIZE, &inf);
            std::cout << off << "memory " << inf << std::endl;
            cl_uint iInf;
            device.getInfo(CL_DEVICE_MAX_COMPUTE_UNITS, &iInf);
            std::cout << off << "compute units " << iInf << std::endl;
            size_t t;
            device.getInfo(CL_DEVICE_MAX_WORK_GROUP_SIZE, &t);
            std::cout << off << "max work group size " << t << std::endl;

        }
    }

public:
	OCLProgram_Implementation(const DataIn &dataIn, DataOut &dataOut) : OCLProgram(dataIn, dataOut)
        {
                /* This is the best place to initialize mKernels member field.
 *                  i.e. mKernels["kernelName"] = Source("kernelFile.cl", true);
 *                                    mKernels["sortElements"] = Source("sortElements.cl",true);*/
                  mKernels["minMaxP"] = Source("minMaxP.cl",true);
                  mKernels["minMaxReduceP"] = Source("minMaxReduceP.cl",true);
		  mKernels["histogram"] = Source("histogram.cl",true);
		  mKernels["zero"] = Source("zero.cl",true);
                  mKernels["cockooHash"] = Source("cockooHash.cl",true);
                  mKernels["cockooFind"] = Source("cockooFind.cl",true);
                  mKernels["prefixSum"] = Source("prefixSum.cl",true);
                  mKernels["prefixSumB"] = Source("prefixSumB.cl",true);
                  mKernels["prefixSumC"] = Source("prefixSumC.cl",true);
                  mKernels["copyByOffset"] = Source("copyByOffset.cl",true);

                  mDataOut.res.assign(1024 * 1024 * 16,0);

	}


	virtual int run(const cl::Context &context, const std::vector<cl::Device> &devices,
		std::map<std::string, cl::Kernel> &kernels, bool verbose)
	{
		/*
 * 		 * Implementation of the main algorithm.
 * 		 		 * Note that you have mDataIn and mDataOut member fields at your disposal.
 *


 * 		 		                  */

           // info(devices);

            cl_int err;

            Stopwatch * stopwatch = NULL;
            if (verbose){
                stopwatch = new Stopwatch(true);
            }


            mCompiledKernels = &kernels;

            size_t size = (mDataIn.set1.size() + mDataIn.set2.size()) * sizeof(unsigned);


            cl::Buffer bufs []= {
                cl::Buffer(context, CL_MEM_READ_WRITE, size, NULL, &err ),  /*in*/
                cl::Buffer(context, CL_MEM_READ_WRITE, size, NULL, &err ),  /*tmp*/
                cl::Buffer(context, CL_MEM_READ_WRITE, size, NULL, &err ),   /*out*/
                cl::Buffer(context, CL_MEM_READ_WRITE, 2 * size, NULL, &err ),   /*COCKOO*/
                cl::Buffer(context, CL_MEM_READ_WRITE, size, NULL, &err ),  /*in2*/
            };
            checkErr(err, "cl::Buffer");
            mBuffers = bufs;

            dbgMsg(verbose, stopwatch,"Creating buffers 1: ");



            cl::CommandQueue commandQueue(context, devices[0], 0, &err);
            checkErr(err, "CommandQueue");
            mCommandQueue = &commandQueue;


            prepareInput();
            dbgMsg(verbose, stopwatch,"Filling buffers: ");

            cockooHash();
            dbgMsg(verbose, stopwatch,"Cockoo hash: ");

            cockooFind();
            dbgMsg(verbose, stopwatch,"Cockoo find: ");

            prefixSum();
            dbgMsg(verbose, stopwatch,"Prefix sum: ");

            runCopyByOffset();
            dbgMsg(verbose, stopwatch,"runCopyByOffset: ");

            if (verbose){
                stopwatch->stop();
                delete stopwatch;
            }

            return 0;	// Success
	}
};





















#endif


